package com.caochenlei.graph;

public class DirectedCycle {
    private boolean[] marked;                   //索引代表顶点，值表示当前顶点是否已经被搜索
    private boolean hasCycle;                   //记录图中是否有环
    private boolean[] onStack;                  //索引代表顶点，使用栈的思想，记录当前顶点有没有已经处于正在搜索的有向路径上

    public DirectedCycle(Digraph G) {
        this.marked = new boolean[G.size()];    //初始化marked数组
        this.hasCycle = false;                  //初始化hasCycle变量
        this.onStack = new boolean[G.size()];   //初始化onStack数组

        for (int v = 0; v < G.size(); v++) {
            if (!marked[v]) {                   //判断当前v顶点有没有被搜索过
                dfs(G, v);                      //如果没有被搜索过，则递归调用dfs方法进行深度搜索
            }
        }
    }

    private void dfs(Digraph G, int v) {        //使用深度优先搜索找出G图中顶点v的所有相通顶点
        marked[v] = true;                       //把v顶点标识为已搜索
        onStack[v] = true;                      //让当前顶点v进栈
        for (Integer w : G.adj(v)) {
            if (!marked[w]) {                   //判断当前w顶点有没有被搜索过
                dfs(G, w);                      //如果没有被搜索过，则递归调用dfs方法进行深度搜索
            }
            if (onStack[w]) {                   //如果顶点w已经被搜索过，则查看顶点w是否在栈中
                hasCycle = true;                //如果在，则证明图中有环，修改hasCycle标记
                return;                         //结束搜索
            }
        }
        onStack[v] = false;                     //当前顶点已经搜索完毕，让当前顶点出栈
    }

    //判断当前有向图G中是否有环
    public boolean hasCycle() {
        return hasCycle;
    }
}
